package TenkindsOfAlgorithm.floyd;

import graph.GraphArray;

/**
 *  * 一种用于寻找给定的加权图中顶点间 最短路径的算法。Floyd
 *  * 图中全部顶点最为出发顶点，每一个顶点都求到其他顶点到路径。
 *  for循环再前套一层Dijkstra算法确实可以得到各个顶点到remaining 顶点，但是这样没有floyd好
 *  换句话说 ： 求任意二条路径最短
 *  https://www.bilibili.com/video/BV1LE411R7CS?from=search&seid=17984164609857649790&spm_id_from=333.337.0.0
 */
public class Floyd {
    public static void main(String[] args) {
        String vertexArray[] = {"A","B","C","D","E","F","G"};
        GraphArray graph = new GraphArray(vertexArray.length);
        // 把节点添加到图中
        for (String s : vertexArray) {
            graph.insertVertex(s);
        }
        graph.insertEdge("A","B",5);
        graph.insertEdge("A","G",2);
        graph.insertEdge("A","C",7);
        graph.insertEdge("B","G",3);
        graph.insertEdge("B","D",9);
        graph.insertEdge("D","F",4);
        graph.insertEdge("F","G",6);
        graph.insertEdge("E","F",5);
        graph.insertEdge("E","G",4);
        graph.insertEdge("E","C",8);
        graph.display();
        graph.floyd();
    }
}
